//给定一个整数数组 A，你可以从某一起始索引出发，跳跃一定次数。在你跳跃的过程中，第 1、3、5... 次跳跃称为奇数跳跃，而第 2、4、6... 次跳跃称为
//偶数跳跃。 
//
// 你可以按以下方式从索引 i 向后跳转到索引 j（其中 i < j）： 
//
// 
// 在进行奇数跳跃时（如，第 1，3，5... 次跳跃），你将会跳到索引 j，使得 A[i] <= A[j]，A[j] 是可能的最小值。如果存在多个这样的索引
// j，你只能跳到满足要求的最小索引 j 上。 
// 在进行偶数跳跃时（如，第 2，4，6... 次跳跃），你将会跳到索引 j，使得 A[i] >= A[j]，A[j] 是可能的最大值。如果存在多个这样的索引
// j，你只能跳到满足要求的最小索引 j 上。 
// （对于某些索引 i，可能无法进行合乎要求的跳跃。） 
// 
//
// 如果从某一索引开始跳跃一定次数（可能是 0 次或多次），就可以到达数组的末尾（索引 A.length - 1），那么该索引就会被认为是好的起始索引。 
//
// 返回好的起始索引的数量。 
//
// 
//
// 示例 1： 
//
// 输入：[10,13,12,14,15]
//输出：2
//解释： 
//从起始索引 i = 0 出发，我们可以跳到 i = 2，（因为 A[2] 是 A[1]，A[2]，A[3]，A[4] 中大于或等于 A[0] 的最小值），然
//后我们就无法继续跳下去了。
//从起始索引 i = 1 和 i = 2 出发，我们可以跳到 i = 3，然后我们就无法继续跳下去了。
//从起始索引 i = 3 出发，我们可以跳到 i = 4，到达数组末尾。
//从起始索引 i = 4 出发，我们已经到达数组末尾。
//总之，我们可以从 2 个不同的起始索引（i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。
// 
//
// 示例 2： 
//
// 输入：[2,3,1,1,4]
//输出：3
//解释：
//从起始索引 i=0 出发，我们依次可以跳到 i = 1，i = 2，i = 3：
//
//在我们的第一次跳跃（奇数）中，我们先跳到 i = 1，因为 A[1] 是（A[1]，A[2]，A[3]，A[4]）中大于或等于 A[0] 的最小值。
//
//在我们的第二次跳跃（偶数）中，我们从 i = 1 跳到 i = 2，因为 A[2] 是（A[2]，A[3]，A[4]）中小于或等于 A[1] 的最大值。A[
//3] 也是最大的值，但 2 是一个较小的索引，所以我们只能跳到 i = 2，而不能跳到 i = 3。
//
//在我们的第三次跳跃（奇数）中，我们从 i = 2 跳到 i = 3，因为 A[3] 是（A[3]，A[4]）中大于或等于 A[2] 的最小值。
//
//我们不能从 i = 3 跳到 i = 4，所以起始索引 i = 0 不是好的起始索引。
//
//类似地，我们可以推断：
//从起始索引 i = 1 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
//从起始索引 i = 2 出发， 我们跳到 i = 3，然后我们就不能再跳了。
//从起始索引 i = 3 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
//从起始索引 i = 4 出发，我们已经到达数组末尾。
//总之，我们可以从 3 个不同的起始索引（i = 1, i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。
// 
//
// 示例 3： 
//
// 输入：[5,1,3,4,2]
//输出：3
//解释： 
//我们可以从起始索引 1，2，4 出发到达数组末尾。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= A.length <= 20000 
// 0 <= A[i] < 100000 
// 
// Related Topics 栈 动态规划 Ordered Map 
// 👍 88 👎 0

package com.leetcode.editor.cn;

import java.util.Arrays;
import java.util.Stack;

//Java：奇偶跳
class P975OddEvenJump {
    public static void main(String[] args) {
        Solution solution = new P975OddEvenJump().new Solution();
        // TO TEST
        int[] nums = {3, 9, 8, 2, 1, 5, 4, 3};
        int[] index = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            index[i] = i;
        }
        //[1, 2, 3, 3, 4, 5, 8, 9]
        //[4, 3, 0, 4, 8, 5, 2, 1]
        solution.quickSort(nums, index, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
        System.out.println(Arrays.toString(index));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int oddEvenJumps(int[] A) {
            int length = A.length;
            //备忘录，从第i个位置起跳是否可行
            boolean[] oddOpt = new boolean[length], evenOpt = new boolean[length];
            //每一个位置的下一个位置
            int[] oddPos = new int[length], evenPos = new int[length];
            //维护排序之后原数组的索引值
            int[] index = new int[length];
            for (int i = 0; i < A.length; i++) {
                index[i] = i;
            }
            int[] newA = Arrays.copyOf(A, length);
            // 计算奇数跳
            fillNextPos(newA, index, oddPos);
//            偶数跳时将 value*1 ，转成和奇数跳一致的方式
            for (int i = 0; i < length; i++) {
                newA[i] = A[i] * -1;
                index[i] = i;
            }
            //计算偶数跳
            fillNextPos(newA, index, evenPos);
            oddOpt[length - 1] = evenOpt[length - 1] = true;
            //起始索引数
            int count = 1;
            for (int i = length - 2; i >= 0; i--) { //该位置奇数跳是否可行、偶数跳是否可行
                int nextPos = oddPos[i];
                if (nextPos == A.length - 1) {
                    oddOpt[i] = true;//到达终点
                } else if (nextPos != 0) {
                    oddOpt[i] = evenOpt[nextPos];//取决于后面是否可行
                }
                if (oddOpt[i]) {
                    count++;
                }
                nextPos = evenPos[i];
                if (nextPos == A.length - 1) {
                    evenOpt[i] = true;//到达终点
                } else if (nextPos != 0) {
                    evenOpt[i] = oddOpt[nextPos];//取决于后面是否可行
                }
            }
            return count;
        }

        private void fillNextPos(int[] newA, int[] index, int[] pos) {
            quickSort(newA, index, 0, newA.length - 1);//value 和key排序
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < newA.length; i++) {//遍历有序数组，使用单调栈找到下一个位置
                while (!stack.isEmpty() && index[i] > stack.peek())//栈不为空且 栈顶小于index
                {
                    pos[stack.pop()] = index[i];//栈顶出栈并将index填入其下一跳跃位置
                }
                stack.push(index[i]);//index入栈
            }
        }

        //改造为稳定的快速排序
        private void quickSort(int arr[], int[] index, int low, int high) {
            int i = low; //i是向后搜索指针
            int j = high;//j是向前搜索指针
            int temp = arr[i];
            int tempIndex = index[i];
            while (i < j) {
                while (i < j && arr[j] >= temp) {
                    if (arr[j] == temp && index[j] < tempIndex) {
                        break;
                    }
                    j--;//arr[j]不小于基准，不用交换，继续向前搜索
                }
                if (i < j) {
                    index[i] = index[j];
                    arr[i++] = arr[j];//比arr[0]小的记录移到前面
                }
                while (i < j && arr[i] <= temp) {
                    if (arr[i] == temp && index[i] > tempIndex) {
                        break;
                    }
                    i++;//arr[i] 不大于基准，不用交换，继续向后搜索
                }
                if (i < j) {
                    index[j] = index[i];
                    arr[j--] = arr[i];//比arr[0]大的记录移到后面
                }
            }
            arr[i] = temp;//确定基准记录位置
            index[i] = tempIndex;
            if (low < i - 1) {
                quickSort(arr, index, low, i - 1); //递归处理左子区
            }
            if (high > i + 1) {
                quickSort(arr, index, i + 1, high); //递归处理右子区
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}